package com.samxcode.leetcode;

/**
 * There are two sorted arrays A and B of size m and n respectively. Find the median of the two
 * sorted arrays. The overall run time complexity should be O(log (m+n)).
 * 
 * 利用二分法的思想
 * 两个数组放在一起，若要寻找合并后第K大的数，如果A[K/2]<B[K/2]，则该数不可能在A[0]-A[K/2]中
 * 每次递归砍去要求的k的一半的数值，时间复杂度O(log(m+n))
 * @author Sam
 *
 */
public class MedianOfTwoSortedArrays {
    
    public static void main(String[] args) {
        int[] A = {1};
        int[] B = {1, 2};
        System.out.println(findMedianSortedArrays(A, B));
    }

    public static double findMedianSortedArrays(int A[], int B[]) {
        int total = A.length + B.length;
        int mid = total / 2;
        if ((total & 1) == 1) {//odd
            return findKth(A, 0, A.length, B, 0, B.length, mid + 1);
        } else {//even
            return (findKth(A, 0, A.length, B, 0, B.length, mid) + findKth(A, 0, A.length, B, 0,
                B.length, mid + 1)) / 2.0;
        }
    }

    //find the Kth digit in the arrays
    private static int findKth(int[] A, int aStart, int aLen, int[] B, int bStart, int bLen, int k) {
        //assure the first array is the array with less elements
        if (aLen > bLen) {
            return findKth(B, bStart, bLen, A, aStart, aLen, k);
        }
        //if A is checked off, return
        if (aLen == 0) {
            return B[bStart + k - 1];
        }
        if (k == 1) {
            return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
        }
        //divide k into two arrays
        int pa = k / 2 < aLen ? k / 2 : aLen;
        int pb = k - pa;
        if (A[aStart + pa - 1] < B[bStart + pb - 1]) {
            return findKth(A, aStart + pa, aLen - pa, B, bStart, bLen, k - pa);
        } else if (A[aStart + pa - 1] > B[bStart + pb - 1]) {
            return findKth(A, aStart, aLen, B, bStart + pb, bLen - pb, k - pb);
        } else {
            return A[aStart + pa - 1];
        }
    }
}
